0-1背包问题的两种解决方法：动态规划与回溯法

1 从前往后遍历：
2 if(j>=w[i])
3 m[i][j]=max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
4 else
5 m[i][j]=m[i-1][j];
6
7 从后往前遍历：
8 if(j>=w[i])
9 m[i][j]=max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
10 else
11 m[i][j]=m[i+1][j];

1 void Backtrack(int i) {
2 if(i > n) { // 到达叶节点
3 bestp = cp;
4 return;
5 }
6 if(cw + w[i] <= c) { // 进入左子树
7 cw += w[i];
8 cp += v[i];
9 Backtrack(i + 1);
10 cw -= w[i];
11 cp -= v[i];
12 }
13 if(Bound(i + 1) > bestp) { // 进入右子树
14 Backtrack(i + 1);
15 }
16}

17 int Bound(int i) { // 计算上界
18 int cleft = c - cw;
19 int b = cp;
20 while(i <= n && w[i] <= cleft) { // 以物品单位重量价值递减序装入物品
21 cleft -= w[i];
22 b += v[i];
23 i++;
24 }
25 if(i <= n) { // 装满背包
26 b += v[i] * (cleft / w[i]);
27 }
28 return b;
29}